import random, copy
import numpy as np

def get_slices(board, pos, radius):
        return [__get_slice(board, pos, radius, 'h'),\
                __get_slice(board, pos, radius, 'v'),\
                __get_diagonal(board, pos, radius, 'd'),\
                __get_diagonal(board, pos, radius, 'u')]

def __get_slice(board, pos, radius, direction='h'):
    board_size = board.shape[0]
    def bound_index(idx, direction='h'):
        if idx < 0:
            return 0
        if direction =='h' and idx >= board_size:
            return board_size
        if direction =='v' and idx >= board_size:
            return board_size
        return idx
    row, col = pos
    if direction == 'h':
        hl, hr = bound_index(col-radius), bound_index(col+radius+1)
        slice_ = board[row, hl:hr]
    elif direction == 'v':
        vl, vr = bound_index(row-radius), bound_index(row+radius+1)
        slice_ = board[vl:vr, col]
    return slice_.copy()

def __get_diagonal(board, pos, radius, direction='d'):
    board_size = board.shape[0]
    row, col = pos
    diag = []
    if direction == 'd':
        for i in xrange(-radius, radius + 1):
            if min(row+i, col+i) < 0:
                continue
            if row+i >= board_size or col+i >= board_size:
                break
            diag.append(board[row+i, col+i])
    elif direction == 'u':
        for i in xrange(-radius, radius + 1):
            if row-i >= board_size or col+i < 0:
                continue
            if row-i < 0 or col+i >= board_size:
                break
            diag.append(board[row-i, col+i])
    return np.array(diag)

EMPTY = 0
WHITE = 1
BLACK = -1

class Gobang(object):
    def __init__(self, board_size):
        self.board_size = board_size
        self.n = 5
        self.__create_game()

    def __create_game(self):
        board = np.zeros((self.board_size, self.board_size), dtype=np.int8)
        self.board = board
        self.cur_player = WHITE
        self.is_over = False
        self.history = []

    def step(self, player, pos):
        if  self.is_over or player != self.cur_player:
            return False
        if self.reachable(pos):
            print 'player', (3 - player) / 2, 'move', pos
            self.board[pos] = player
            self.history.append((player, pos))
            if self.check_win(pos):
                print 'game over'
                self.is_over = True
            self.cur_player =  -player
        return True

    def back(self):
        if len(self.history) == 0:
            return
        player, pos = self.history.pop()
        self.board[pos] = EMPTY
        self.cur_player = player

    def reachable(self, pos):
        return self.board[pos] == EMPTY

    def check_win(self, pos):
        def is_win(array, player):
            num = 0
            for p in array:
                if p == player:
                    num += 1
                    if num == self.n:
                        return True
                else:
                    num = 0
            return False
        player = self.board[pos]
        if player != WHITE and player != BLACK:
            return False
        radius = self.n - 1
        slices = get_slices(self.board, pos, radius)
        for s in slices:
            if is_win(s, player):
                return True
        return False

if __name__ == '__main__':
    # game = Gobang((30,30))
    # for i in range(1, 6):
    #     game.board[i,6-i] = 1
    # print game.board[:10,:10]
    # print game.check_win((4,1))
    pass